/*
*	记忆化搜索
*/


//斐波那契数-记忆化搜索
//https://leetcode.cn/problems/fibonacci-number/submissions/
// class Solution {
// public:
//     int fib(int n) {
//         vector<int> grid(n+1,-1);
//         dfs(grid,n);
//         return grid[n];
//     }

//     int dfs(vector<int>& grid,int n)
//     {
//         if(n == 0 || n == 1) grid[n] = n;
//         else if(grid[n] == -1) grid[n] = dfs(grid,n-1) + dfs(grid,n-2);
//         return grid[n];
//     }
// };


//不同路径-记忆化搜索
//https://leetcode.cn/problems/unique-paths/description/
// class Solution {
// public:
//     int uniquePaths(int m, int n) {
//         vector<vector<int>> grid(m+1,vector<int>(n+1,-1));
//         return dfs(grid,m,n);
//     }

//     int dfs(vector<vector<int>>& grid,int m,int n)
//     {
//         if(m == 0 || n == 0) return 0;
//         if(m == 1 && n == 1) return 1;
//         if(grid[m-1][n] == -1) grid[m-1][n] = dfs(grid,m-1,n);
//         if(grid[m][n-1] == -1) grid[m][n-1] = dfs(grid,m,n-1);
//         return grid[m-1][n]+grid[m][n-1];
//     }
// };


//最长递增子序列
//https://leetcode.cn/problems/longest-increasing-subsequence/description/
// class Solution {
//     int n = 0;
// public:
//     int lengthOfLIS(vector<int>& nums) {
//         n = nums.size();
//         int ret = 0;
//         vector<int> grid(n,-1);
//         for(int i = 0;i<n;++i)
//             ret = max(ret,dfs(nums,grid,i));
        
//         return ret;
//     }

//     int dfs(vector<int>& nums,vector<int>& grid,int pos) {
//         if(grid[pos] != -1) return grid[pos]; //如果以前遍历过 则直接使用
//         int ret = 1; //只要能进来 就表示有一个元素
//         for(int i = pos+1;i<n;++i)
//             if(nums[i] > nums[pos]) ret = max(ret,dfs(nums,grid,i)+1);

//         grid[pos] = ret;
//         return ret;
//     }
// };


//猜数字大小
//https://leetcode.cn/problems/guess-number-higher-or-lower-ii/description/
// class Solution {
// public:
//     int getMoneyAmount(int n) {
//         vector<vector<int>> grid(n+1,vector<int>(n+1));
//         return dfs(0,n,grid);
//     }

//     int dfs(int begin,int end,vector<vector<int>>& grid)
//     {
//         //如果begin==end说明找到了不需要支付
//         //如果begin>end 则越界了
//         if(begin >= end) return 0;
//         if(grid[begin][end] != 0) return grid[begin][end];
//         int ret = INT_MAX;
//         for(int i = begin;i<=end;++i)
//         {
//             int left = dfs(begin,i-1,grid);
//             int right = dfs(i+1,end,grid);
//             //选择ret 和 支付第i个位置和后续猜数字的钱
//             //后续的钱只有在最大值中选最小值即可
//             ret = min(ret,i+max(left,right));
//         }
//         grid[begin][end] = ret;
//         return ret;
//     }
// };


//矩阵中的最长递增路径
//https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/submissions/
// class Solution {
//     int m = 0,n = 0;
//     int dx[4] = {-1,1,0,0},dy[4] = {0,0,-1,1};
// public:
//     int longestIncreasingPath(vector<vector<int>>& matrix) {
//         m = matrix.size(),n = matrix[0].size();
//         vector<vector<int>> grid(m,vector<int>(n));
//         int ret = 0;
//         //选择起点
//         for(int i = 0;i<m;++i)
//             for(int k = 0;k<n;++k)
//                 ret = max(dfs(matrix,i,k,grid),ret);

//         return ret;
//     }

//     int dfs(vector<vector<int>>& matrix,int x,int y,vector<vector<int>>& grid)
//     {
//         if(grid[x][y]) return grid[x][y];
//         int ret = 1;
//         for(int i = 0;i<4;++i)
//         {
//             int px = x+dx[i],py = y+dy[i];
//             if(px<m && px>=0 && py<n && py>=0 && matrix[x][y]<matrix[px][py])
//                 ret = max(ret,dfs(matrix,px,py,grid)+1);
//         }
//         grid[x][y] = ret;
//         return ret;
//     }
// };


